{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Count Servers that Communicate"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #depth-first-search #breadth-first-search #union-find #array #counting #matrix"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #深度优先搜索 #广度优先搜索 #并查集 #数组 #计数 #矩阵"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: countServers"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #统计参与通信的服务器"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>这里有一幅服务器分布图，服务器的位置标识在&nbsp;<code>m * n</code>&nbsp;的整数矩阵网格&nbsp;<code>grid</code>&nbsp;中，1 表示单元格上有服务器，0 表示没有。</p>\n",
    "\n",
    "<p>如果两台服务器位于同一行或者同一列，我们就认为它们之间可以进行通信。</p>\n",
    "\n",
    "<p>请你统计并返回能够与至少一台其他服务器进行通信的服务器的数量。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2019/11/24/untitled-diagram-6.jpg\" style=\"height: 203px; width: 202px;\"></p>\n",
    "\n",
    "<pre><strong>输入：</strong>grid = [[1,0],[0,1]]\n",
    "<strong>输出：</strong>0\n",
    "<strong>解释：</strong>没有一台服务器能与其他服务器进行通信。</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<p><strong><img alt=\"\" src=\"https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2019/11/24/untitled-diagram-4-1.jpg\" style=\"height: 203px; width: 203px;\"></strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>grid = [[1,0],[1,1]]\n",
    "<strong>输出：</strong>3\n",
    "<strong>解释：</strong>所有这些服务器都至少可以与一台别的服务器进行通信。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2019/11/24/untitled-diagram-1-3.jpg\" style=\"height: 443px; width: 443px;\"></p>\n",
    "\n",
    "<pre><strong>输入：</strong>grid = [[1,1,0,0],[0,0,1,0],[0,0,1,0],[0,0,0,1]]\n",
    "<strong>输出：</strong>4\n",
    "<strong>解释：</strong>第一行的两台服务器互相通信，第三列的两台服务器互相通信，但右下角的服务器无法与其他服务器通信。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>m == grid.length</code></li>\n",
    "\t<li><code>n == grid[i].length</code></li>\n",
    "\t<li><code>1 &lt;= m &lt;= 250</code></li>\n",
    "\t<li><code>1 &lt;= n &lt;= 250</code></li>\n",
    "\t<li><code>grid[i][j] == 0 or 1</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [count-servers-that-communicate](https://leetcode.cn/problems/count-servers-that-communicate/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [count-servers-that-communicate](https://leetcode.cn/problems/count-servers-that-communicate/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[[1,0],[0,1]]', '[[1,0],[1,1]]', '[[1,1,0,0],[0,0,1,0],[0,0,1,0],[0,0,0,1]]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countServers(self, grid: List[List[int]]) -> int:\n",
    "        row_dict={}\n",
    "        col_dict={}\n",
    "        m=len(grid)\n",
    "        n=len(grid[0])\n",
    "        flag=False\n",
    "        count=0\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j]==1:\n",
    "                    if i not in row_dict:\n",
    "                        row_dict[i] = 1\n",
    "                    else:\n",
    "                        row_dict[i]+=1\n",
    "                    if j not in col_dict:\n",
    "                        col_dict[j] = 1\n",
    "                    else:\n",
    "                        col_dict[j]+=1\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j]==1:\n",
    "                    if row_dict[i] > 1 or col_dict[j] > 1:\n",
    "                        count+=1\n",
    "        return count\n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countServers(self, grid: List[List[int]]) -> int:\n",
    "        m, n = len(grid),  len(grid[0])\n",
    "        row = [0]*m\n",
    "        column = [0] * n\n",
    "        ans = 0\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == 1:\n",
    "                    row[i] += 1\n",
    "                    column[j] += 1\n",
    "                    ans += 1\n",
    "        for i in range(m):\n",
    "            if row[i] == 1:\n",
    "                for j in range(n):\n",
    "                    if grid[i][j] and column[j] == 1:\n",
    "                        ans -= 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countServers(self, grid: List[List[int]]) -> int:\n",
    "        rows, cols = defaultdict(int), defaultdict(int)\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == 1:\n",
    "                    rows[i] += 1\n",
    "                    cols[j] += 1\n",
    "        ans = 0\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == 1 and (rows[i] > 1 or cols[j] > 1):\n",
    "                    ans += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import collections\n",
    "from typing import List\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def countServers(self, grid: List[List[int]]) -> int:\n",
    "        col, row = collections.Counter(), collections.Counter()\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == 1:\n",
    "                    row[i] += 1\n",
    "                    col[j] += 1\n",
    "\n",
    "        res = 0\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == 1 and (row[i] > 1 or col[j] > 1):\n",
    "                    res += 1\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countServers(self, grid: List[List[int]]) -> int:\n",
    "        col = [sum(l) for l in zip(*grid)]\n",
    "        ans = sum(col)\n",
    "        for l in grid:\n",
    "            if sum(l) == 1 == col[l.index(1)]:\n",
    "                ans -= 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countServers(self, grid: List[List[int]]) -> int:\n",
    "        vis1 = [0] * (len(grid) + 1)  # 横\n",
    "        vis2 = [0] * (len(grid[0]) + 1)  # 列\n",
    "        cnt = 0\n",
    "        n = len(grid)\n",
    "        m = len(grid[0])\n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "                if grid[i][j] == 1:\n",
    "                    vis1[i] += 1\n",
    "                    vis2[j] += 1\n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "                if grid[i][j] == 1 and (vis1[i] >= 2 or vis2[j] >= 2):\n",
    "                    cnt += 1\n",
    "        return cnt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countServers(self, grid: List[List[int]]) -> int:\n",
    "        col = [sum(l) for l in zip(*grid)]\n",
    "        ans = sum(col)\n",
    "        for l in grid:\n",
    "            if sum(l) == 1:\n",
    "                ans -= col[l.index(1)] == 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countServers(self, grid: List[List[int]]) -> int:\n",
    "        cs_num = 0\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        row = [0] * m\n",
    "        col = [0] * n\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j]:\n",
    "                    row[i] += 1\n",
    "                    col[j] += 1\n",
    "        for idx, val in enumerate(row):\n",
    "            if val > 1:\n",
    "                cs_num += val\n",
    "            elif val == 1:\n",
    "                if col[grid[idx].index(1)] > 1:\n",
    "                    cs_num += 1\n",
    "        return cs_num\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countServers(self, grid: List[List[int]]) -> int:\n",
    "        m = len(grid)\n",
    "        n = len(grid[0])\n",
    "\n",
    "        row = [0]*m\n",
    "        col = [0]*n\n",
    "\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == 1:\n",
    "                   row[i] += 1 \n",
    "                   col[j] += 1\n",
    "        \n",
    "        ans = 0\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == 1 and (row[i]>1 or col[j]>1):\n",
    "                    ans += 1\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countServers(self, grid: List[List[int]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        rows, cols = Counter(), Counter()\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == 1:\n",
    "                    rows[i] += 1\n",
    "                    cols[j] += 1\n",
    "        \n",
    "        ans = 0\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == 1 and (rows[i] > 1 or cols[j] > 1):\n",
    "                    ans += 1\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import collections\n",
    "from typing import List\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def countServers(self, grid: List[List[int]]) -> int:\n",
    "        col, row = collections.Counter(), collections.Counter()\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == 1:\n",
    "                    row[i] += 1\n",
    "                    col[j] += 1\n",
    "\n",
    "        res = 0\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == 1 and (row[i] > 1 or col[j] > 1):\n",
    "                    res += 1\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countServers(self, grid: List[List[int]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        row, col = [0]*m, [0]*n\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == 1:\n",
    "                    row[i] = row[i] + 1\n",
    "                    col[j] = col[j] + 1\n",
    "        result = 0\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if (row[i]>1 or col[j]>1) and grid[i][j] == 1:\n",
    "                    result = result + 1\n",
    "        return result "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countServers(self, grid: List[List[int]]) -> int:\n",
    "        m,n = len(grid),len(grid[0])\n",
    "        row,col = dict(),dict() #分别记录服务所在行和列服务器台数\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j]==1:\n",
    "                    if i not in row:\n",
    "                        row[i] = 1\n",
    "                    else:\n",
    "                        row[i] += 1\n",
    "                    if j not in col:\n",
    "                        col[j] = 1\n",
    "                    else:\n",
    "                        col[j] += 1\n",
    "        rs = 0\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j]==1 and (row[i]>1 or col[j]>1):\n",
    "                    rs += 1\n",
    "        return rs"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countServers(self, grid: List[List[int]]) -> int:\n",
    "        row_sum = [sum(row) for row in grid]\n",
    "        col_sum = [sum([row[i] for row in grid]) for i in range(len(grid[0]))]\n",
    "        total = sum(row_sum)\n",
    "        for i in range(len(row_sum)):\n",
    "            for j in range(len(col_sum)):\n",
    "                if row_sum[i] == col_sum[j] == grid[i][j] == 1:\n",
    "                    total -= 1\n",
    "        return total\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countServers(self, grid: List[List[int]]) -> int:\n",
    "        col = [sum(l) for l in zip(*grid)]\n",
    "        ans = sum(col)\n",
    "        for l in grid:\n",
    "            if sum(l) == 1:\n",
    "                ans -= col[l.index(1)] == 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countServers(self, grid: List[List[int]]) -> int:\n",
    "        m = len(grid)\n",
    "        n = len(grid[0])\n",
    "        r = [0]*m\n",
    "        c = [0]*n\n",
    "        ans = 0\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == 1:\n",
    "                    r[i]+=1\n",
    "                    c[j]+=1\n",
    "        return sum(\n",
    "            grid[i][j] and (r[i] > 1 or c[j] > 1)\n",
    "            for i in range(m)\n",
    "            for j in range(n)\n",
    "        )\n",
    "\n",
    "\n",
    "                    \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countServers(self, grid: List[List[int]]) -> int:\n",
    "        col = [sum(l) for l in zip(*grid)]\n",
    "        ans = sum(col)\n",
    "        for l in grid:\n",
    "            if sum(l) == 1 == col[l.index(1)]:\n",
    "                ans -= 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countServers(self, grid: List[List[int]]) -> int:\n",
    "        cnt, m, n = 0, len(grid), len(grid[0])\n",
    "        rows = [sum(x) for x in grid]\n",
    "        cols = [sum(x) for x in zip(*grid)]\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] and (rows[i] > 1 or cols[j] > 1):\n",
    "                    cnt += 1\n",
    "        return cnt\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countServers(self, grid: List[List[int]]) -> int:\n",
    "        m = len(grid)\n",
    "        n = len(grid[0])\n",
    "        rows = [0] * m\n",
    "        cols = [0] * n\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == 1:\n",
    "                    rows[i] += 1\n",
    "                    cols[j] += 1\n",
    "        ans = 0\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == 1 and (rows[i] >= 2 or cols[j] >= 2):\n",
    "                    ans += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countServers(self, grid: List[List[int]]) -> int:\n",
    "        col = [sum(l) for l in zip(*grid)]\n",
    "        ans = sum(col)\n",
    "        for l in grid:\n",
    "            if sum(l) == 1 == col[l.index(1)]:\n",
    "                ans -= 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countServers(self, grid: List[List[int]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        row, col = collections.Counter(), collections.Counter()\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == 1:\n",
    "                    row[i] += 1\n",
    "                    col[j] += 1\n",
    "        ans = 0\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == 1 and (row[i] > 1 or col[j] > 1):\n",
    "                    ans += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countServers(self, grid: List[List[int]]) -> int:\n",
    "        row_sum = [sum(row) for row in grid]\n",
    "        col_sum = [sum([row[i] for row in grid]) for i in range(len(grid[0]))]\n",
    "        print(row_sum)\n",
    "        print(col_sum)\n",
    "        total = sum(row_sum)\n",
    "        for i in range(len(row_sum)):\n",
    "            for j in range(len(col_sum)):\n",
    "                if row_sum[i] == col_sum[j] == grid[i][j] == 1:\n",
    "                    total -= 1\n",
    "\n",
    "        return total\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countServers(self, grid: List[List[int]]) -> int:\n",
    "        cnt, m, n = 0, len(grid), len(grid[0])\n",
    "        rows = [sum(x) for x in grid]\n",
    "        cols = [sum(x) for x in zip(*grid)]\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] and (rows[i] > 1 or cols[j] > 1):\n",
    "                    cnt += 1\n",
    "        return cnt\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countServers(self, grid: List[List[int]]) -> int:\n",
    "        ans=0\n",
    "        dir=[(1,0),(0,1),(0,-1),(-1,0)]\n",
    "        m,n=len(grid),len(grid[0])\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j]==1:\n",
    "                    ans+=1\n",
    "                    flag=False\n",
    "                    for dx,dy in dir:\n",
    "                        x,y=i+dx,j+dy\n",
    "                        while 0<=x<m and 0<=y<n:\n",
    "                            if grid[x][y]==1:\n",
    "                                flag=True\n",
    "                                break\n",
    "                            x+=dx\n",
    "                            y+=dy\n",
    "                        if flag:\n",
    "                            break\n",
    "                    if not flag :ans-=1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def countServers(self, grid: List[List[int]]) -> int:\r\n",
    "        m, n = len(grid), len(grid[0])\r\n",
    "        row, col = [0] * m, [0] * n\r\n",
    "        for i in range(m):\r\n",
    "            for j in range(n):\r\n",
    "                if grid[i][j] == 1:\r\n",
    "                    row[i] += 1\r\n",
    "                    col[j] += 1\r\n",
    "        res = 0\r\n",
    "        for i in range(m):\r\n",
    "            for j in range(n):\r\n",
    "                if grid[i][j] and (row[i] > 1 or col[j] > 1):\r\n",
    "                    res += 1\r\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countServers(self, grid: List[List[int]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        col, row = [0] * m, [0] * n\n",
    "        res = 0\n",
    "\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == 1:\n",
    "                    col[i] += 1\n",
    "                    row[j] += 1\n",
    "        \n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == 1 and (col[i] > 1 or row[j] > 1):\n",
    "                    res += 1\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countServers(self, grid: List[List[int]]) -> int:\n",
    "        row_sum = [sum(row) for row in grid]\n",
    "        col_sum = [sum([row[i] for row in grid]) for i in range(len(grid[0]))]\n",
    "        print(row_sum)\n",
    "        print(col_sum)\n",
    "        total = sum(row_sum)\n",
    "        for i in range(len(row_sum)):\n",
    "            for j in range(len(col_sum)):\n",
    "                if row_sum[i] == col_sum[j] == grid[i][j] == 1:\n",
    "                    total -= 1\n",
    "\n",
    "        return total\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countServers(self, grid: List[List[int]]) -> int:\n",
    "        lom = len(grid[0])\n",
    "        lin = len(grid)\n",
    "        lin_sum = 0\n",
    "        lom_sum = 0\n",
    "        result = [[0] * lom for i in range(lin)]\n",
    "        # print (result)\n",
    "        result_sum = 0\n",
    "        result1 = [0] * lom\n",
    "        result2 = [0] * lin\n",
    "        for i in range(lom):\n",
    "            for j in range(lin):\n",
    "                result1[i] += grid[j][i]\n",
    "        for i in range(lin):\n",
    "            result2[i] = sum(grid[i])\n",
    "            for j in range(lom):\n",
    "                if(grid[i][j] == 1 and (result1[j] > 1 or result2[i] > 1)):\n",
    "                    result[i][j] = 1\n",
    "            result_sum += sum(result[i])\n",
    "        return result_sum\n",
    " \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countServers(self, grid: List[List[int]]) -> int:\n",
    "        m = len(grid)\n",
    "        n = len(grid[0])\n",
    "        latitude = [0] * n\n",
    "        longitude = [0] * m\n",
    "        volume = set()\n",
    "\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j]:\n",
    "                    longitude[i] = longitude[i] + 1\n",
    "                    latitude[j] = latitude[j] + 1\n",
    "\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] and (latitude[j] > 1 or longitude[i] > 1):\n",
    "                    volume.add((i, j))\n",
    "        return len(volume)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countServers(self, grid: List[List[int]]) -> int:\n",
    "        m = len(grid)\n",
    "        n = len(grid[0])\n",
    "        row = m*[0]\n",
    "        col = n*[0]\n",
    "        sum = 0\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == 1:\n",
    "                    row[i] += 1\n",
    "                    col[j] += 1\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == 1 and (row[i] > 1 or col[j] > 1):\n",
    "                    sum += 1\n",
    "        return sum\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countServers(self, grid: List[List[int]]) -> int:\n",
    "        grid_new = []\n",
    "        for i, row_ele in enumerate(grid):\n",
    "            for j, col_ele in enumerate(row_ele):\n",
    "                if col_ele == 1:\n",
    "                    grid_new.append([i, j])\n",
    "        rowindex = {}\n",
    "        colindex = {}\n",
    "        for pos in grid_new:\n",
    "            rowindex[pos[0]] = rowindex.get(pos[0], 0) + 1\n",
    "            colindex[pos[1]] = colindex.get(pos[1], 0) + 1\n",
    "\n",
    "        res = len(grid_new)\n",
    "        for pos in grid_new:\n",
    "            if rowindex[pos[0]] == 1 and colindex[pos[1]] == 1:\n",
    "                res -= 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countServers(self, grid: List[List[int]]) -> int:\n",
    "        '''\n",
    "        哈希表\n",
    "        1、先统计每一行，每一列的服务器数量。\n",
    "        2、维护一个哈希表，如果数量大于二加入哈希集合。\n",
    "        '''\n",
    "\n",
    "        rst = set()\n",
    "\n",
    "        rows = len(grid)\n",
    "        cols = len(grid[0])\n",
    "\n",
    "        rows_flag = [0] * rows\n",
    "        cols_flag = [0] * cols\n",
    "\n",
    "        # 一次遍历记录每一行每一列服务器数量\n",
    "        for i in range(rows):\n",
    "            for j in range(cols):\n",
    "                if grid[i][j]:\n",
    "                    rows_flag[i] += 1\n",
    "                    cols_flag[j] += 1\n",
    "\n",
    "        print(rows_flag)\n",
    "        print(cols_flag)\n",
    "\n",
    "        # 分别对目标列和行遍历\n",
    "        for i in range(rows):\n",
    "            if rows_flag[i] >= 2:\n",
    "                for j in range(cols):\n",
    "                    if grid[i][j]:\n",
    "                        rst.add((i,j))\n",
    "\n",
    "        for j in range(cols):\n",
    "            if cols_flag[j] >= 2:\n",
    "                for i in range(rows):\n",
    "                    if grid[i][j]:\n",
    "                        rst.add((i,j))\n",
    "\n",
    "        return len(rst)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countServers(self, grid: List[List[int]]) -> int:\n",
    "        visited = set()\n",
    "        ncol = len(grid[0])\n",
    "\n",
    "        for row in range(len(grid)):\n",
    "            if sum(grid[row]) > 1:\n",
    "                for col in range(len(grid[0])):\n",
    "                    if grid[row][col] == 1:\n",
    "                        visited.add((row, col))\n",
    "        \n",
    "        for col in range(len(grid[0])):\n",
    "            if sum([grid[row][col] for row in range(len(grid))]) > 1:\n",
    "                for row in range(len(grid)):\n",
    "                    if grid[row][col] == 1:\n",
    "                        visited.add((row, col))\n",
    "        \n",
    "        return len(visited)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countServers(self, arr: List[List[int]]) -> int:\n",
    "        res_dict = set()\n",
    "        for i in range(len(arr)):\n",
    "            if arr[i].count(1) > 1:\n",
    "                for j in range(len(arr[i])):\n",
    "                    if arr[i][j] == 1:\n",
    "                        res_dict.add((i, j))\n",
    "        tmp = list(zip(*arr))\n",
    "        for i in range(len(tmp)):\n",
    "            if tmp[i].count(1) > 1:\n",
    "                for j in range(len(tmp[i])):\n",
    "                    if tmp[i][j] == 1:\n",
    "                        res_dict.add((j, i))\n",
    "        return len(res_dict)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countServers(self, grid: List[List[int]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        latitude, longitude = [0] * n, [0] * m\n",
    "        volume = set()\n",
    "\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j]:\n",
    "                    longitude[i] = longitude[i] + 1\n",
    "                    latitude[j] = latitude[j] + 1\n",
    "\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] and (latitude[j] > 1 or longitude[i] > 1):\n",
    "                    volume.add((i, j))\n",
    "        return len(volume)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countServers(self, grid: List[List[int]]) -> int:\n",
    "        x = set()\n",
    "        for row_id, row in enumerate(grid):\n",
    "            if row.count(1) > 1:\n",
    "                for col_id, col in enumerate(row):\n",
    "                    if col == 1:\n",
    "                        x.add((row_id, col_id))\n",
    "\n",
    "        for row_id, row in enumerate(zip(*grid)):\n",
    "            if row.count(1) > 1:\n",
    "                for col_id, col in enumerate(row):\n",
    "                    if col == 1:\n",
    "                        x.add((col_id, row_id))\n",
    "\n",
    "        return len(x)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countServers(self, grid: List[List[int]]) -> int:\n",
    "        m = len(grid)\n",
    "        n = len(grid[0])\n",
    "        latitude = [0] * n\n",
    "        longitude = [0] * m\n",
    "        volume = set()\n",
    "        for i,x in enumerate(grid):\n",
    "            longitude[i] = sum(x)\n",
    "        for i in range(n):\n",
    "            val = 0\n",
    "            for j in range(m):\n",
    "                val = val + grid[j][i]\n",
    "            latitude[i] = val\n",
    "\n",
    "        for i in range(m):\n",
    "            if longitude[i] > 1:\n",
    "                for j in range(n):\n",
    "                    if grid[i][j]:\n",
    "                        volume.add((i,j))\n",
    "        for j in range(n):\n",
    "            if latitude[j]>1:\n",
    "                for i in range(m):\n",
    "                    if grid[i][j]:\n",
    "                        volume.add((i,j))\n",
    "        return len(volume)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countServers(self, grid: List[List[int]]) -> int:\n",
    "        m = len(grid)\n",
    "        n = len(grid[0])\n",
    "        ans = list()\n",
    "        for i in range(m):\n",
    "            grid[i].append(0)\n",
    "        grid.append([0]*(n+1))\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == 1:\n",
    "                    ans.append([i,j])\n",
    "        a = len(ans)\n",
    "        print(a)\n",
    "        for i in range(a):\n",
    "            grid[ans[i][0]][ans[i][1]] = 0\n",
    "            # print(ans,grid[0:n][j])\n",
    "            if 1 not in grid[ans[i][0]]:\n",
    "                for k in range(m):\n",
    "                    if grid[k][ans[i][1]] == 1:\n",
    "                        break\n",
    "                    elif grid[k][ans[i][1]] == 0 and k < m - 1:\n",
    "                        continue\n",
    "                    else:\n",
    "                        a -= 1\n",
    "            grid[ans[i][0]][ans[i][1]] = 1\n",
    "        return a"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countServers(self, grid: List[List[int]]) -> int:\n",
    "        hash_map = {}\n",
    "        r_grid = list(zip(*grid))\n",
    "        for i, row in enumerate(grid):\n",
    "            if row.count(1) > 1:\n",
    "                for j, one in enumerate(row):\n",
    "                    if one:\n",
    "                        hash_map.setdefault((i, j), 1)\n",
    "        for j, col in enumerate(r_grid):\n",
    "            if col.count(1) > 1:\n",
    "                for i, one in enumerate(col):\n",
    "                    if one:\n",
    "                        hash_map.setdefault((i, j), 1)\n",
    "        return len(hash_map)\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import deque\n",
    "class Solution:\n",
    "    def countServers(self, grid: List[List[int]]) -> int:\n",
    "        res = 0\n",
    "        reverse_matrix = [[] for _ in range(len(grid[0]))]\n",
    "        matrix = [[] for _ in range(len(grid))]\n",
    "        for j in range(len(grid[0])):\n",
    "            for i in range(len(grid)):\n",
    "                if grid[i][j]:\n",
    "                    reverse_matrix[j].append((i,j))\n",
    "                    matrix[i].append((i,j))\n",
    "        for i in range(len(grid)):\n",
    "            for j in range(len(grid[0])):\n",
    "                if grid[i][j] and (len(reverse_matrix[j]) > 1 or len(matrix[i]) > 1):\n",
    "                    res += 1\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countServers(self, arr: List[List[int]]) -> int:\n",
    "        res_dict = set()\n",
    "        for i in range(len(arr)):\n",
    "            if arr[i].count(1) > 1:\n",
    "                for j in range(len(arr[i])):\n",
    "                    if arr[i][j] == 1:\n",
    "                        res_dict.add((i, j))\n",
    "        tmp = list(zip(*arr))\n",
    "        for i in range(len(tmp)):\n",
    "            if tmp[i].count(1) > 1:\n",
    "                for j in range(len(tmp[i])):\n",
    "                    if tmp[i][j] == 1:\n",
    "                        res_dict.add((j, i))\n",
    "        return len(res_dict)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "from itertools import chain\n",
    "from functools import reduce\n",
    "\n",
    "class Solution:\n",
    "    def countServers(self, grid: List[List[int]]) -> int:\n",
    "\n",
    "        m, n = len(grid), len(grid[0])\n",
    "\n",
    "        r_rec = defaultdict(list)\n",
    "        c_rec = defaultdict(list)\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j]:\n",
    "                    r_rec[i].append(i*n + j)\n",
    "                    c_rec[j].append(i*n + j)\n",
    "\n",
    "        tmp = [r_list for r_list in r_rec.values() if len(r_list)>1]\n",
    "        tmp.extend([c_list for c_list in c_rec.values() if len(c_list)>1])\n",
    "        \n",
    "        return len(set(reduce(lambda x,y: x+y, tmp))) if tmp else 0\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countServers(self, grid: List[List[int]]) -> int:\n",
    "        ans = 0\n",
    "        for i in range(len(grid)):\n",
    "            if sum(grid[i]) >= 2:\n",
    "                ans += sum(grid[i])\n",
    "                for j in range(len(grid[i])):\n",
    "                    if grid[i][j] == 1:\n",
    "                        grid[i][j] = 2\n",
    "        print(ans)\n",
    "        print(grid)\n",
    "        for j in range(len(grid[0])):\n",
    "            count1 = 0\n",
    "            count2 = 0\n",
    "            for i in range(len(grid)):\n",
    "                if grid[i][j] == 1:\n",
    "                    count1 += 1\n",
    "                if grid[i][j] == 2:\n",
    "                    count2 += 1\n",
    "                \n",
    "            if count1 + count2 >= 2:\n",
    "                ans += count1\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countServers(self, grid: List[List[int]]) -> int:\n",
    "        record = set()\n",
    "        def sun_count1(grid):\n",
    "            for row, i in enumerate(grid):\n",
    "                if sum(i) <= 1:\n",
    "                    continue\n",
    "                for col, j in enumerate(i):\n",
    "                    if j == 1:\n",
    "                        record.add((row, col))\n",
    "        def sun_count2(grid):\n",
    "            for row, i in enumerate(grid):\n",
    "                if sum(i) <= 1:\n",
    "                    continue\n",
    "                for col, j in enumerate(i):\n",
    "                    if j == 1:\n",
    "                        record.add((col, row))\n",
    "\n",
    "\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        grid_1 = [[grid[i][j]  for i in range(m)] for j in range(n)]\n",
    "\n",
    "\n",
    "        sun_count1(grid)\n",
    "        sun_count2(grid_1)\n",
    "        return len(record)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countServers(self, grid: List[List[int]]) -> int:\n",
    "        \"\"\"\n",
    "        m == grid.length\n",
    "        n == grid[i].length\n",
    "        1 <= m <= 250\n",
    "        1 <= n <= 250\n",
    "        grid[i][j] == 0 or 1\n",
    "        \"\"\"\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        ret = 0\n",
    "        seen = set()\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                found = False\n",
    "                if grid[i][j] == 1 and (i, j) not in seen:\n",
    "                    dq = Deque([(i, j)])\n",
    "                    while dq:\n",
    "                        a, b = dq.popleft()\n",
    "                        seen.add((a, b))\n",
    "                        for k in range(m):\n",
    "                            if k == a:\n",
    "                                continue\n",
    "                            if grid[k][b] == 1 and (k, b) not in seen:\n",
    "                                seen.add((k, b))\n",
    "                                dq.append((k, b))\n",
    "                                ret += 1\n",
    "                                found = True\n",
    "                        for k in range(n):\n",
    "                            if k == b:\n",
    "                                continue\n",
    "                            if grid[a][k] == 1 and (a, k) not in seen:\n",
    "                                seen.add((a, k))\n",
    "                                dq.append((a, k))\n",
    "                                ret += 1\n",
    "                                found = True\n",
    "                    if found:\n",
    "                        ret += 1\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countServers(self, grid: List[List[int]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        valid = set()\n",
    "        for i in range(m):\n",
    "            if sum(grid[i]) > 1:\n",
    "                for j in range(n):\n",
    "                    if grid[i][j] == 1:\n",
    "                        valid.add((i, j))\n",
    "        for j in range(n):\n",
    "            if sum(list(zip(*grid))[j]) > 1:\n",
    "                for i in range(m):\n",
    "                    if grid[i][j] == 1:\n",
    "                        valid.add((i, j))\n",
    "        return len(valid)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countServers(self, grid: List[List[int]]) -> int:\n",
    "        m,n=len(grid),len(grid[0])\n",
    "        ans=[]\n",
    "        for i in range(m):\n",
    "            temp=[]\n",
    "            for j in range(n):\n",
    "                if grid[i][j]:\n",
    "                    temp.append((i,j))\n",
    "            if len(temp)>1:\n",
    "                ans.extend(temp)\n",
    "        for i in range(n):\n",
    "            temp=[]\n",
    "            for j in range(m):\n",
    "                if grid[j][i]:\n",
    "                    temp.append((j,i))\n",
    "            if len(temp)>1:\n",
    "                ans.extend(temp)\n",
    "        return len(set(ans))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countServers(self, grid: List[List[int]]) -> int:\n",
    "        l1=[]\n",
    "        l2=[]\n",
    "        res=0\n",
    "        for i in range(len(grid)):\n",
    "            l1.append(sum(grid[i]))\n",
    "        for j in range(len(grid[0])):\n",
    "            l2.append(sum([grid[i][j] for i in range(len(grid))]))\n",
    "        print(l1,l2,grid)\n",
    "        for i in range(len(grid)):\n",
    "            for j in range(len(grid[0])):\n",
    "                if (l1[i]>1 or l2[j]>1) and grid[i][j]==1:\n",
    "                    print(i,j)\n",
    "                    res+=1\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countServers(self, grid: List[List[int]]) -> int:\n",
    "        m,n=len(grid),len(grid[0])\n",
    "        s = set()\n",
    "        d = [[] for _ in range(n)]\n",
    "        q = [[] for _ in range(m)]\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j]==1:\n",
    "                    d[j].append((i,j))\n",
    "                    q[i].append((i,j))\n",
    "        for tt in d:\n",
    "            if len(tt)>1:\n",
    "                for item in tt:\n",
    "                    s.add(item)\n",
    "        for qq in q:\n",
    "            if len(qq)>1:\n",
    "                for item in qq:\n",
    "                    s.add(item)\n",
    "        return len(s)\n",
    "                \n",
    "\n",
    "\n",
    "        \n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countServers(self, grid: List[List[int]]) -> int:\n",
    "        n=sum([sum(s) for s in grid])\n",
    "        m1,m2=[],[]\n",
    "        n1=len(grid)\n",
    "        for i in range(n1):\n",
    "            if sum(grid[n1-1-i])>=2:\n",
    "                m1.append(n1-1-i)\n",
    "        grid=list(zip(*grid))\n",
    "        n2=len(grid)\n",
    "        for i in range(n2):\n",
    "            if sum(grid[n2-1-i])>=2:\n",
    "                m2.append(n2-1-i)\n",
    "        for s in m2:\n",
    "            del grid[s]\n",
    "        if not grid:\n",
    "            return n\n",
    "        grid=list(zip(*grid))\n",
    "        for s in m1:\n",
    "            del grid[s]\n",
    "        return n-sum([sum(s) for s in grid])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countServers(self, grid: List[List[int]]) -> int:\n",
    "        mp_i = defaultdict(set)\n",
    "        mp_j = defaultdict(set)\n",
    "        for i in range(len(grid)):\n",
    "            for j in range(len(grid[0])):\n",
    "                if grid[i][j]:\n",
    "                    mp_i[i].add(j)\n",
    "                    mp_j[j].add(i)\n",
    "\n",
    "        ans = set()\n",
    "        for i in mp_i:\n",
    "            if len(mp_i[i]) > 1:\n",
    "                for j in mp_i[i]:\n",
    "                    ans.add((i, j))\n",
    "        for j in mp_j:\n",
    "            if len(mp_j[j]) > 1:\n",
    "                for i in mp_j[j]:\n",
    "                    ans.add((i, j))\n",
    "        return len(ans)\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countServers(self, grid: List[List[int]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        pair = []\n",
    "        for i in range(m):\n",
    "            tmp = []\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == 1:\n",
    "                    tmp.append((i, j))\n",
    "            if len(tmp) > 1:\n",
    "                pair.extend(tmp)\n",
    "\n",
    "        for i in range(n):\n",
    "            tmp = []\n",
    "            for j in range(m):\n",
    "                if grid[j][i] == 1:\n",
    "                    tmp.append((j, i))\n",
    "            if len(tmp) > 1:\n",
    "                pair.extend(tmp)\n",
    "\n",
    "        dic = set()\n",
    "        for i in pair:\n",
    "            dic.add(i)\n",
    "        return len(dic)\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countServers(self, grid: List[List[int]]) -> int:\n",
    "        n, m = len(grid), len(grid[0])\n",
    "        rowStore, colStore = collections.defaultdict(list), collections.defaultdict(list)\n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "                if grid[i][j] == 1:\n",
    "                    rowStore[i].append((i, j,))\n",
    "                    colStore[j].append((i, j,))\n",
    "        \n",
    "        result = 0\n",
    "        for r, indexes in rowStore.items():\n",
    "            for nr, nc in indexes:\n",
    "                if grid[nr][nc] == 1:\n",
    "                    count = self.search(grid, nr, nc, rowStore, colStore)\n",
    "                    if count != 1:\n",
    "                        result += count\n",
    "        return result\n",
    "\n",
    "    def search(self, grid, r, c, rowStore, colStore):\n",
    "        queue = collections.deque([(r, c,)])\n",
    "        nextQueue = collections.deque()\n",
    "        result = 0\n",
    "        grid[r][c] = 2\n",
    "        while queue:\n",
    "            row, col = queue.pop()\n",
    "            result += 1\n",
    "            for nr, nc in rowStore[row]:\n",
    "                if grid[nr][nc] == 1 and (nr, nc,) != (r, c,):\n",
    "                    grid[nr][nc] = 2\n",
    "                    nextQueue.appendleft((nr, nc,))\n",
    "            for nr, nc in colStore[col]:\n",
    "                if grid[nr][nc] == 1 and (nr, nc,) != (r, c,):\n",
    "                    grid[nr][nc] = 2\n",
    "                    nextQueue.appendleft((nr, nc,))\n",
    "            if not queue:\n",
    "                queue = nextQueue.copy()\n",
    "                nextQueue.clear()\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countServers(self, grid: List[List[int]]) -> int:\n",
    "        rows = [0] * len(grid)\n",
    "        cols = [0] * len(grid[0])\n",
    "\n",
    "        for l in range(len(grid)):\n",
    "            for c in range(len(grid[0])):\n",
    "                if grid[l][c]:\n",
    "                    rows[l] += 1\n",
    "                    cols[c] += 1\n",
    "        \n",
    "        return sum(tuple(grid[l][c] and (rows[l] > 1 or cols[c] > 1) for l in range(len(grid)) for c in range(len(grid[0]))))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countServers(self, grid: List[List[int]]) -> int:\n",
    "        m,n = len(grid),len(grid[0])\n",
    "        counted = [[False for j in range(n)] for i in range(m)]\n",
    "        row = [[] for i in range(m)]\n",
    "        col = [[] for j in range(n)]\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == 1:\n",
    "                    row[i].append((i,j))\n",
    "                    col[j].append((i,j))\n",
    "        ans = 0\n",
    "        for i in range(m):\n",
    "            if len(row[i]) >= 2:\n",
    "                for x,y in row[i]:\n",
    "                    counted[x][y] = True\n",
    "                    ans += 1\n",
    "        for j in range(n):\n",
    "            if len(col[j]) >= 2:\n",
    "                for x,y in col[j]:\n",
    "                    if not counted[x][y]:\n",
    "                        ans +=1\n",
    "        return ans\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countServers(self, grid: List[List[int]]) -> int:\n",
    "        row,column=defaultdict(set),defaultdict(set)\n",
    "        m,n=len(grid),len(grid[0])\n",
    "        result=set()\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j]:\n",
    "                    row[i].add((i,j))\n",
    "                    column[j].add((i,j))\n",
    "        for r in row.values():\n",
    "            if len(r)>1:\n",
    "                result.update(r)\n",
    "        for c in column.values():\n",
    "            if len(c)>1:\n",
    "                result.update(c)\n",
    "        return len(result)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "from collections import defaultdict\n",
    "\n",
    "\n",
    "class UFS:\n",
    "\n",
    "    def __init__(self, items):\n",
    "        self.parents = {i: i for i in items}\n",
    "        self.count = len(items)\n",
    "\n",
    "    def find(self, item):\n",
    "        if self.parents[item] != item:\n",
    "            self.parents[item] = self.find(self.parents[item])  # 很关键\n",
    "        return self.parents[item]\n",
    "\n",
    "    def union(self, item1, item2):\n",
    "        root1, root2 = self.find(item1), self.find(item2)\n",
    "        if root1 != root2:\n",
    "            self.parents[root2] = root1\n",
    "            self.count -= 1\n",
    "\n",
    "    def is_connect(self, item1, item2):\n",
    "        return self.find(item1) == self.find(item2)\n",
    "\n",
    "    @property\n",
    "    def groups(self):\n",
    "        ans = defaultdict(list)\n",
    "        for item in self.parents.keys():\n",
    "            ans[self.find(item)].append(item)\n",
    "        return ans\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def countServers(self, grid: List[List[int]]) -> int:\n",
    "\n",
    "        service = [(h, w) for w in range(len(grid[0])) for h in range(len(grid)) if grid[h][w]]\n",
    "        ufs = UFS(list(range(len(service))))\n",
    "\n",
    "        def union_list(l):                              # 把列表中所有对象连接起来，组成连通域\n",
    "            if len(l) <= 1:\n",
    "                return\n",
    "            for item1, item2 in zip(l, l[1:]):\n",
    "                ufs.union(item1, item2)\n",
    "\n",
    "        dict_h, dict_w = defaultdict(list), defaultdict(list)\n",
    "        for i, (h, w) in enumerate(service):\n",
    "            dict_h[h].append(i)\n",
    "            dict_w[w].append(i)\n",
    "\n",
    "        for v in dict_h.values():\n",
    "            union_list(v)\n",
    "        for v in dict_w.values():\n",
    "            union_list(v)\n",
    "\n",
    "        ans = sum(len(net) for net in ufs.groups.values() if len(net) > 1)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countServers(self, grid: List[List[int]]) -> int:\n",
    "        cnt = 0\n",
    "        ##行可通信服务器数量\n",
    "        for i in range(0, len(grid)):\n",
    "            first_index_x = -1\n",
    "            first_index_y = -1\n",
    "            tmp_cnt = 0\n",
    "            for j in range(0, len(grid[i])):\n",
    "                if grid[i][j] == 1:  ##如果当前节点有服务器\n",
    "                    ##服务器计数+1\n",
    "                    tmp_cnt += 1\n",
    "                    ##如果是第一个服务器，记录当前位置\n",
    "                    if tmp_cnt == 1:\n",
    "                        first_index_x = i \n",
    "                        first_index_y = j \n",
    "                    elif first_index_x != -1 and first_index_y != -1:\n",
    "                        ##修改第一个发现服务器节点\n",
    "                        grid[first_index_x][first_index_y] += 1\n",
    "                        first_index_x = -1\n",
    "                        first_index_y = -1\n",
    "                    if tmp_cnt > 1:\n",
    "                        ##修改当前节点\n",
    "                        grid[i][j] += 1\n",
    "            if tmp_cnt > 1:\n",
    "                cnt += tmp_cnt\n",
    "        print('debug0:', cnt, grid)\n",
    "        ##列可通信服务器数量\n",
    "        for j in range(0, len(grid[0])):\n",
    "            first_index_x = -1\n",
    "            first_index_y = -1\n",
    "            tmp_cnt = 0\n",
    "            unvalid_cnt = 0\n",
    "            for i in range(0, len(grid)):\n",
    "                if grid[i][j] >= 1:  ##如果当前节点有服务器\n",
    "                    ##服务器计数+1\n",
    "                    tmp_cnt += 1\n",
    "                    print('ddd:', i, j, grid[i][j])\n",
    "                    if grid[i][j] > 1:\n",
    "                        unvalid_cnt += 1\n",
    "                    ##如果是第一个服务器，记录当前位置\n",
    "                    if tmp_cnt == 1:\n",
    "                        first_index_x = i \n",
    "                        first_index_y = j \n",
    "                    elif first_index_x != -1 and first_index_y != -1:\n",
    "                        ##修改第一个发现服务器节点\n",
    "                        grid[first_index_x][first_index_y] += 1\n",
    "                        first_index_x = -1\n",
    "                        first_index_y = -1\n",
    "                    if tmp_cnt > 1:\n",
    "                        ##修改当前节点\n",
    "                        grid[i][j] += 1\n",
    "            print('debug:', tmp_cnt, unvalid_cnt)\n",
    "            if tmp_cnt > 1:\n",
    "                cnt += tmp_cnt - unvalid_cnt\n",
    "        return cnt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def countServers(self, grid: List[List[int]]) -> int:\n",
    "        m=len(grid[0])\n",
    "        n=len(grid)\n",
    "\n",
    "        tempGrid=[[ 0 for i in range(m) ] for j in range(n)]\n",
    "        r=0\n",
    "        for i in range(m):\n",
    "            currCount=0\n",
    "            start=-1\n",
    "            for j in range(n):\n",
    "                if grid[j][i]==1:\n",
    "                    if currCount==0:\n",
    "                        start=j\n",
    "                        currCount=currCount+1\n",
    "                    else:\n",
    "                        currCount=currCount+1\n",
    "                        tempGrid[j][i]=1\n",
    "\n",
    "            if currCount>1:\n",
    "                tempGrid[start][i]=1\n",
    "                r=r+currCount\n",
    "        print(tempGrid)\n",
    "        for j in range(n):\n",
    "            currCount=0\n",
    "            tempCount=0\n",
    "            start=-1\n",
    "            for i in range(m):\n",
    "                if grid[j][i]==1:\n",
    "                    if tempCount==0:\n",
    "                        start=i\n",
    "                        tempCount=tempCount+1\n",
    "                    else:\n",
    "                        tempCount=tempCount+1\n",
    "                        if tempGrid[j][i]==0:\n",
    "                            currCount=currCount+1\n",
    "                            tempGrid[j][i]=1\n",
    "\n",
    "\n",
    "            if tempCount>1 and tempGrid[j][start]==0:\n",
    "                tempGrid[j][start]=1\n",
    "                currCount=currCount+1\n",
    "            print(currCount)\n",
    "            r=r+currCount\n",
    "        return r"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countServers(self, grid: List[List[int]]) -> int:\n",
    "        class UnionFind():\n",
    "            def __init__(self,grid):\n",
    "                m = len(grid)\n",
    "                n = len(grid[0])\n",
    "                self.parent = [0]*(m*n)\n",
    "                self.rank=[0]*(m*n)\n",
    "                for i in range(m):\n",
    "                    for j in range(n):\n",
    "                        self.parent[i*n+j] = i*n+j\n",
    "                        if grid[i][j] == 1:\n",
    "                            self.rank[i*n+j] = 1\n",
    "            def find(self,i):\n",
    "                if self.parent[i] != i:\n",
    "                    self.parent[i] = self.find(self.parent[i])\n",
    "                return self.parent[i]\n",
    "            def merge(self,i,j):\n",
    "                p_i,p_j = self.find(i),self.find(j)\n",
    "                if p_i == p_j:\n",
    "                    return \n",
    "                if self.rank[p_j]>self.rank[p_i]:\n",
    "                    p_i,p_j = p_j,p_i\n",
    "                self.parent[p_j] = p_i\n",
    "                # print(self.rank[p_j],self.rank[p_i],'@')\n",
    "                self.rank[p_i] += self.rank[p_j]\n",
    "                self.rank[p_j] =0\n",
    "        m = len(grid)\n",
    "        if m==0:\n",
    "            return 0\n",
    "        n = len(grid[0])\n",
    "        un = UnionFind(grid)\n",
    "        # print(un.parent)\n",
    "        # print(un.rank)\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == 1:\n",
    "                    # 考虑同列并且只考虑右边\n",
    "                    for k in range(j+1,n):\n",
    "                        if grid[i][k] == 1:\n",
    "                            # print('同列',j)\n",
    "                            un.merge(i*n+j,i*n+k)\n",
    "                    # 考虑同列并且只考虑上方\n",
    "                    for k in range(i+1,m):\n",
    "                        if grid[k][j] == 1:\n",
    "                            # print('同行',i)\n",
    "                            un.merge(i*n+j,k*n+j)\n",
    "        print(un.parent)\n",
    "        print(un.rank)\n",
    "        count = 0\n",
    "        for i in un.rank:\n",
    "            if i >1:\n",
    "                count += i\n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import copy\n",
    "class Solution:\n",
    "    def countServers(self, grid: List[List[int]]) -> int:\n",
    "        length = len(grid[0])\n",
    "        high = len(grid)\n",
    "        global giao\n",
    "        giao = copy.deepcopy(grid[:])\n",
    "        num = 0\n",
    "        for i in range(high):\n",
    "            if grid[i].count(1) >= 2:\n",
    "                for j in range(length):\n",
    "                    if grid[i][j] == 1:\n",
    "                        giao[i][j] = 2\n",
    "        for i in range(length):\n",
    "            list1 = []\n",
    "            for j in range(high):\n",
    "                list1.append(grid[j][i])\n",
    "            if list1.count(1) >= 2:\n",
    "                for n in range(high):\n",
    "                    if grid[n][i] == 1:\n",
    "                        giao[n][i] = 2\n",
    "\n",
    "        for i in range(high):\n",
    "            for j in range(length):\n",
    "                if giao[i][j] == 2:\n",
    "                    num += 1\n",
    "        return num\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from queue import Queue\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def countServers(self, grid: List[List[int]]) -> int:\n",
    "        count = 0\n",
    "        node = []\n",
    "        node_idx_dict = collections.defaultdict(int)\n",
    "        for i, line in enumerate(grid):\n",
    "            for j, point in enumerate(line):\n",
    "                if point:\n",
    "                    node.append([i, j])\n",
    "                    node_idx_dict[i * 250 + j] = len(node) - 1\n",
    "        is_visited = [0 for i in range(len(node))]\n",
    "        for node_idx in range(len(node)):\n",
    "            if not is_visited[node_idx]:\n",
    "                q = Queue()\n",
    "                q.put(node[node_idx])\n",
    "                is_visited[node_idx] = 1\n",
    "                tmp = 1\n",
    "                while q.qsize() != 0:\n",
    "                    head = q.get()\n",
    "                    for i in range(len(grid[0])):\n",
    "                        if grid[head[0]][i] == 1 and not is_visited[node_idx_dict[head[0] * 250 + i]]:\n",
    "                            q.put([head[0], i])\n",
    "                            is_visited[node_idx_dict[head[0] * 250 + i]] = 1\n",
    "                            tmp += 1\n",
    "                    for i in range(len(grid)):\n",
    "                        if grid[i][head[1]] == 1 and not is_visited[node_idx_dict[i * 250 + head[1]]]:\n",
    "                            q.put([i, head[1]])\n",
    "                            is_visited[node_idx_dict[i * 250 + head[1]]] = 1\n",
    "                            tmp += 1\n",
    "                if tmp > 1:\n",
    "                    count += tmp\n",
    "        return count\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class UnionFind:\n",
    "    def __init__(self, n):\n",
    "        self.parent = [i for i in range(n)]\n",
    "        self.size = [1 for i in range(n)]\n",
    "\n",
    "    def union(self, x, y):\n",
    "        root_x, root_y = self.find(x), self.find(y)\n",
    "        if root_x!=root_y:\n",
    "            self.parent[root_y] = root_x\n",
    "            self.size[root_x] += self.size[root_y]\n",
    "\n",
    "    def find(self, x):\n",
    "        if self.parent[x] != x:\n",
    "            self.parent[x] = self.find(self.parent[x])\n",
    "        return self.parent[x]\n",
    "\n",
    "    def count_con(self):\n",
    "        count = 0\n",
    "        for i in range(len(self.parent)):\n",
    "            if self.parent[i]==i and self.size[i]>1:\n",
    "                count += self.size[i]\n",
    "        return count\n",
    "\n",
    "class Solution:\n",
    "    def countServers(self, grid: List[List[int]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        def gridToIndex(x, y):\n",
    "            return x * n + y\n",
    "        # 统计每行，每列的服务器数量\n",
    "        row_dict, col_dict = collections.defaultdict(list), collections.defaultdict(list)\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == 1:\n",
    "                    row_dict[i].append((i, j))\n",
    "                    col_dict[j].append((i, j))\n",
    "\n",
    "        # 并查集合并\n",
    "        union_find = UnionFind(m * n)\n",
    "        for value in row_dict.values():\n",
    "            if len(value) > 1:\n",
    "                for i in range(1, len(value)):\n",
    "                    union_find.union(gridToIndex(*value[0]), gridToIndex(*value[i]))\n",
    "        for value in col_dict.values():\n",
    "            if len(value) > 1:\n",
    "                for i in range(1, len(value)):\n",
    "                    union_find.union(gridToIndex(*value[0]), gridToIndex(*value[i]))\n",
    "\n",
    "        return union_find.count_con()\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countServers(self, grid: List[List[int]]) -> int:\n",
    "        l = len(grid)\n",
    "        l2 = len(grid[0])\n",
    "        bank = [[0 for i in range(l2)] for j in range(l)]\n",
    "        res = 0\n",
    "        for i in range(l):\n",
    "            if  sum(grid[i]) >=2 :\n",
    "                for j in range(l2):\n",
    "                    if grid[i][j] == 1:\n",
    "                        bank[i][j] += 1\n",
    "                        res += 1\n",
    "        grid = list(zip(*grid))\n",
    "        bank = list(zip(*bank))\n",
    "        for i in range(l2):\n",
    "            if  sum(grid[i]) >=2 :\n",
    "                for j in range(l):\n",
    "                    if grid[i][j] == 1 and bank[i][j] == 0:\n",
    "                        res += 1\n",
    "        \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class UnionFindSet:\n",
    "    def __init__(self, n: int) -> None:\n",
    "        self.parent = [i for i in range(n)]\n",
    "        self.rank = [0 for _ in range(n)]\n",
    "\n",
    "    def find(self, x: int) -> int:\n",
    "        if self.parent[x] != x:\n",
    "            self.parent[x] = self.find(self.parent[x])\n",
    "        return self.parent[x]\n",
    "\n",
    "    def union(self, x: int, y: int) -> None:\n",
    "        xroot, yroot = self.find(x), self.find(y)\n",
    "\n",
    "        if xroot != yroot:\n",
    "            if self.rank[xroot] < self.rank[yroot]:\n",
    "                xroot, yroot = yroot, xroot\n",
    "            self.parent[yroot] = xroot\n",
    "\n",
    "            if self.rank[xroot] == self.rank[yroot]:\n",
    "                self.rank[xroot] += 1\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def countServers(self, grid: List[List[int]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "\n",
    "        rows = defaultdict(set)\n",
    "        cols = defaultdict(set)\n",
    "\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == 1:\n",
    "                    rows[i].add(j)\n",
    "                    cols[j].add(i)\n",
    "\n",
    "        ufs = UnionFindSet(m * n)\n",
    "\n",
    "        for x, yset in rows.items():\n",
    "            y = yset.pop()\n",
    "            for ny in yset:\n",
    "                ufs.union(x * n + y, x * n + ny)\n",
    "\n",
    "        for y, xset in cols.items():\n",
    "            x = xset.pop()\n",
    "            for nx in xset:\n",
    "                ufs.union(x * n + y, nx * n + y)\n",
    "\n",
    "        counter = defaultdict(int)\n",
    "        for x in range(m):\n",
    "            for y in range(n):\n",
    "                if grid[x][y] == 1:\n",
    "                    counter[ufs.find(x * n + y)] += 1\n",
    "\n",
    "        res = sum([val for val in counter.values() if val > 1])\n",
    "\n",
    "        return res\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class UnionFind:\n",
    "    def __init__(self,matrix):\n",
    "        self.fathers = {}\n",
    "        self.sizes = {}\n",
    "        for i in range(len(matrix)):\n",
    "            for j in range(len(matrix[0])):\n",
    "                if matrix[i][j] == 1:\n",
    "                    self.fathers[(i,j)] = (i,j)\n",
    "                    self.sizes[(i,j)] = 1\n",
    "        \n",
    "    def find(self,node):\n",
    "        father = self.fathers[node]\n",
    "        if father != node:\n",
    "            if father != self.fathers[father]:\n",
    "                self.sizes[father] -= 1\n",
    "            father = self.find(father)\n",
    "\n",
    "        self.fathers[node] = father\n",
    "        return father\n",
    "\n",
    "    def union(self,node1,node2):\n",
    "        if self.same_group(node1,node2):\n",
    "            return\n",
    "        \n",
    "        root1 = self.find(node1)\n",
    "        root2 = self.find(node2)\n",
    "\n",
    "        size1 = self.sizes[root1]\n",
    "        size2 = self.sizes[root2]\n",
    "\n",
    "        if size1 >= size2:\n",
    "            self.fathers[root2] = root1\n",
    "            self.sizes[root1] = size1+size2\n",
    "            self.sizes[root2] = 1\n",
    "        else:\n",
    "            self.fathers[root1] = root2\n",
    "            self.sizes[root2] = size1+size2\n",
    "            self.sizes[root1] = 1\n",
    "\n",
    "\n",
    "\n",
    "    def same_group(self,node1,node2):\n",
    "        return self.find(node1)==self.find(node2)\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def countServers(self, grid: List[List[int]]) -> int:\n",
    "        uf = UnionFind(grid)\n",
    "\n",
    "        \n",
    "        for i in range(len(grid)):\n",
    "            for j in range(len(grid[0])):\n",
    "                node1 = (i,j)\n",
    "                if grid[i][j] == 0:\n",
    "                    continue\n",
    "                for k in range(j+1,len(grid[0])):\n",
    "                    node2 = (i,k)\n",
    "                    if grid[i][k]==1:\n",
    "                        uf.union(node1,node2)\n",
    "                        break\n",
    "\n",
    "                for l in range(i+1,len(grid)):\n",
    "                    node2 = (l,j)\n",
    "                    if grid[l][j]==1:\n",
    "                        uf.union(node1,node2)\n",
    "                        break\n",
    "                \n",
    "                \n",
    "\n",
    "        print(uf.fathers)\n",
    "        print(uf.sizes)\n",
    "\n",
    "        res = 0\n",
    "        for key,val in uf.sizes.items():\n",
    "            if val>1: res+=val\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countServers(self, grid: List[List[int]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        coordinate_valid = []\n",
    "        for i in range(m):\n",
    "            server_columns = 0\n",
    "            coordinate_columns = []\n",
    "            for j in range(n):\n",
    "                if grid[i][j] == 1:\n",
    "                    server_columns += 1\n",
    "                    coordinate_columns.append([i, j])\n",
    "                    if server_columns >= 2:\n",
    "                        coordinate_valid.extend(coordinate_columns)\n",
    "        # print(coordinate_valid)\n",
    "        for i in range(n):\n",
    "            server_rows = 0\n",
    "            coordinate_rows = []\n",
    "            for j in range(m):\n",
    "                if grid[j][i] == 1:\n",
    "                    server_rows += 1\n",
    "                    coordinate_rows.append([j, i])\n",
    "                    if server_rows >= 2:\n",
    "                        coordinate_valid.extend(coordinate_rows)\n",
    "        # print(coordinate_valid)\n",
    "        ans = []\n",
    "        for l in coordinate_valid:\n",
    "            if l not in ans:\n",
    "                ans.append(l)\n",
    "        return len(ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Union:\n",
    "    def __init__(self, n):\n",
    "        self.parent = [i for i in range(n)]\n",
    "        self.size = [1] * n \n",
    "    def find_parent(self, a):\n",
    "        if a == self.parent[a]:\n",
    "            return a \n",
    "        return self.find_parent(self.parent[a])\n",
    "    def connect(self, a,b):\n",
    "        a_pa = self.find_parent(a)\n",
    "        b_pa = self.find_parent(b)\n",
    "        if a_pa == b_pa:\n",
    "            return False\n",
    "        if self.size[a] < self.size[b]:\n",
    "            self.size[b] += self.size[a]\n",
    "            self.parent[a_pa] = b_pa\n",
    "        else: \n",
    "            self.size[a] += self.size[b]\n",
    "            self.parent[b_pa] = a_pa\n",
    "        return True\n",
    "class Solution:\n",
    "    def countServers(self, grid: List[List[int]]) -> int:\n",
    "        v = {}\n",
    "        u = 0\n",
    "        for i in range(len(grid)):\n",
    "            for j in range(len(grid[0])):\n",
    "                if grid[i][j] == 1:\n",
    "                    v[(i, j)] = [0, u]\n",
    "                    u += 1\n",
    "        print(u)\n",
    "        union_po = Union(u)\n",
    "        for i in range(len(grid)):\n",
    "            if sum(grid[i]) > 1:\n",
    "                der = None\n",
    "                for j in range(len(grid[0])):\n",
    "                    if grid[i][j] == 1 and der is None:\n",
    "                        der = v[(i, j)]\n",
    "                    elif grid[i][j] == 1 and der is not None:\n",
    "                        der_1 = v[(i, j)]\n",
    "                        if union_po.connect(der[1], der_1[1]):\n",
    "                            der_1[0] = 1\n",
    "                            der[0] = 1\n",
    "                            print(der)\n",
    "        # print(v)\n",
    "        for j in range(len(grid[0])):\n",
    "            a = sum(grid[q][j] for q in range(len(grid)))\n",
    "            if a > 1:\n",
    "                der = None\n",
    "                for i in range(len(grid)):\n",
    "                    if grid[i][j] == 1 and der is None:\n",
    "                        der = v[(i, j)]\n",
    "                    elif grid[i][j] == 1 and der is not None:\n",
    "                        der_1 = v[(i, j)]\n",
    "                        if union_po.connect(der[1], der_1[1]):\n",
    "                            der_1[0] = 1\n",
    "                            der[0] = 1\n",
    "        print(v)\n",
    "        yyy = sum([j[0] for i,j in v.items() ])\n",
    "        return yyy\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import deque\n",
    "class Solution:\n",
    "    def countServers(self, grid: List[List[int]]) -> int:\n",
    "        self.grid = grid\n",
    "        self.res = 0\n",
    "        self.record = [[0 for _ in range(len(grid[0]))] for _ in range(len(grid))]\n",
    "        computers = [(i,j) for i in range(len(grid)) for j in range(len(grid[0])) if grid[i][j]]\n",
    "        self.reverse_matrix = [[] for _ in range(len(grid[0]))]\n",
    "        self.matrix = [[] for _ in range(len(grid))]\n",
    "        for j in range(len(grid[0])):\n",
    "            for i in range(len(grid)):\n",
    "                if grid[i][j]:\n",
    "                    self.reverse_matrix[j].append((i,j))\n",
    "                    self.matrix[i].append((i,j))\n",
    "        for i,j in computers:\n",
    "            if self.record[i][j]==0:\n",
    "                self.dfs(i,j)\n",
    "        return self.res\n",
    "    \n",
    "    def dfs(self,i,j):\n",
    "        self.record[i][j] = 1\n",
    "        flag = 0\n",
    "        dfs_deque = deque([(i,j)])\n",
    "        while len(dfs_deque):\n",
    "            cur_node = dfs_deque.popleft()\n",
    "            i1, j1 = cur_node\n",
    "            # 纵线通信\n",
    "            for i2, j2 in self.reverse_matrix[j1]:\n",
    "                if self.record[i2][j2]==0:\n",
    "                    self.record[i2][j2] = 1\n",
    "                    dfs_deque.append((i2,j2))\n",
    "                    self.res += 1\n",
    "                    flag = 1\n",
    "            # 横向通信\n",
    "            for i2, j2 in self.matrix[i1]:\n",
    "                if self.record[i2][j2]==0:\n",
    "                    self.record[i2][j2] = 1\n",
    "                    dfs_deque.append((i2,j2))\n",
    "                    self.res += 1\n",
    "                    flag = 1\n",
    "        if flag:\n",
    "            self.res += 1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class UnionFind:\n",
    "    def __init__(self,size):\n",
    "        self.root=[0]*size\n",
    "        self.cnt=[1]*size\n",
    "        for i in range(size):\n",
    "            self.root[i]=i\n",
    "\n",
    "    def FindRoot(self,index):\n",
    "        while index!=self.root[index]:\n",
    "            index=self.root[index]\n",
    "        return index\n",
    "\n",
    "    def Connect(self,p,q):\n",
    "        rootP=self.FindRoot(p)\n",
    "        rootQ=self.FindRoot(q)\n",
    "        if rootP==rootQ:\n",
    "            return\n",
    "        if self.cnt[rootP]>=self.cnt[rootQ]:\n",
    "            self.root[rootQ]=rootP\n",
    "            self.cnt[rootP]+=self.cnt[rootQ]\n",
    "        elif self.cnt[rootQ]>self.cnt[rootP]:\n",
    "            self.root[rootP]=rootQ\n",
    "            self.cnt[rootQ]+=self.cnt[rootP]\n",
    "\n",
    "    def isConnect(self,p,q):\n",
    "        return self.FindRoot(p)==self.FindRoot(q)\n",
    "\n",
    "class Solution:\n",
    "    def countServers(self, grid: List[List[int]]) -> int:\n",
    "        m=len(grid)\n",
    "        n=len(grid[0])\n",
    "        uf=UnionFind(255*255)\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j]==1:\n",
    "                    for k in range(i+1,m):\n",
    "                        if grid[k][j]==1:\n",
    "                            uf.Connect(i*n+j,k*n+j)\n",
    "                    for k in range(j+1,n):\n",
    "                        if grid[i][k]==1:\n",
    "                            uf.Connect(i*n+j,i*n+k)\n",
    "        myset=set()\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if grid[i][j]==1:\n",
    "                    rootij=uf.FindRoot(i*n+j)\n",
    "                    if uf.cnt[rootij]>1:\n",
    "                        myset.add(rootij)\n",
    "        ans=0\n",
    "        for mybit in myset:\n",
    "            ans+=uf.cnt[mybit]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class UnionFind:\n",
    "    def __init__(self,matrix):\n",
    "        self.fathers = {}\n",
    "        self.sizes = {}\n",
    "        for i in range(len(matrix)):\n",
    "            for j in range(len(matrix[0])):\n",
    "                if matrix[i][j] == 1:\n",
    "                    self.fathers[(i,j)] = (i,j)\n",
    "                    self.sizes[(i,j)] = 1\n",
    "        \n",
    "    def find(self,node):\n",
    "        father = self.fathers[node]\n",
    "        if father != node:\n",
    "            if father != self.fathers[father]:\n",
    "                self.sizes[father] -= 1\n",
    "            father = self.find(father)\n",
    "\n",
    "        self.fathers[node] = father\n",
    "        return father\n",
    "\n",
    "    def union(self,node1,node2):\n",
    "        if self.same_group(node1,node2):\n",
    "            return\n",
    "        \n",
    "        root1 = self.find(node1)\n",
    "        root2 = self.find(node2)\n",
    "\n",
    "        size1 = self.sizes[root1]\n",
    "        size2 = self.sizes[root2]\n",
    "\n",
    "        if size1 >= size2:\n",
    "            self.fathers[root2] = root1\n",
    "            self.sizes[root1] = size1+size2\n",
    "            self.sizes[root2] = 1\n",
    "        else:\n",
    "            self.fathers[root1] = root2\n",
    "            self.sizes[root2] = size1+size2\n",
    "            self.sizes[root1] = 1\n",
    "\n",
    "\n",
    "\n",
    "    def same_group(self,node1,node2):\n",
    "        return self.find(node1)==self.find(node2)\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def countServers(self, grid: List[List[int]]) -> int:\n",
    "        uf = UnionFind(grid)\n",
    "\n",
    "        \n",
    "        for i in range(len(grid)):\n",
    "            for j in range(len(grid[0])):\n",
    "                node1 = (i,j)\n",
    "                if grid[i][j] == 0:\n",
    "                    continue\n",
    "                for k in range(j+1,len(grid[0])):\n",
    "                    node2 = (i,k)\n",
    "                    if grid[i][k]==1:\n",
    "                        uf.union(node1,node2)\n",
    "                        break\n",
    "\n",
    "                for l in range(i+1,len(grid)):\n",
    "                    node2 = (l,j)\n",
    "                    if grid[l][j]==1:\n",
    "                        uf.union(node1,node2)\n",
    "                        break\n",
    "                \n",
    "                \n",
    "        res = 0\n",
    "        for key,val in uf.sizes.items():\n",
    "            if val>1: res+=val\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countServers(self, grid: List[List[int]]) -> int:\n",
    "        res = 0\n",
    "        mark = [[False] * len(grid[0]) for _ in range(len(grid))]\n",
    "        for j, row in enumerate(grid):\n",
    "            cnt = 0\n",
    "            t = []\n",
    "            for i, s in enumerate(row):\n",
    "\n",
    "                if s == 1:\n",
    "                    t.append(i)\n",
    "                    cnt += 1\n",
    "            if cnt > 1:\n",
    "                for m in t:\n",
    "                    mark[j][m] = True\n",
    "                    res += 1\n",
    "\n",
    "        grid = list(zip(*grid))\n",
    "        mark = list(zip(*mark))\n",
    "        mark = [list(g) for g in mark]\n",
    "        for j, row in enumerate(grid):\n",
    "            cnt = 0\n",
    "            t = []\n",
    "            for i, s in enumerate(row):\n",
    "\n",
    "                if s == 1:\n",
    "                    t.append(i)\n",
    "                    cnt += 1\n",
    "            if cnt > 1:\n",
    "                for m in t:\n",
    "                    if not mark[j][m]:\n",
    "                        mark[j][m] = True\n",
    "                        res += 1\n",
    "\n",
    "        return res\n",
    "\n",
    "                        \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "                    \n",
    "        \n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countServers(self, grid: List[List[int]]) -> int:\n",
    "        # 同行同列可以通信\n",
    "        # 返回能够通信的服务器数量\n",
    "        m,n = len(grid),len(grid[0])\n",
    "        res = 0\n",
    "        prefix = MatrixSum(grid)\n",
    "        for i in range(0,m):\n",
    "            for j in range(0,n):\n",
    "                if grid[i][j]!=1:continue\n",
    "                if grid[i][j]==1 and (prefix.query(i,0,i+1,n)>1 or prefix.query(0,j,m,j+1)>1):\n",
    "                    res+=1\n",
    "        return res\n",
    "\n",
    "class MatrixSum:\n",
    "    def __init__(self, matrix: List[List[int]]):\n",
    "        m, n = len(matrix), len(matrix[0])\n",
    "        s = [[0] * (n + 1) for _ in range(m + 1)]\n",
    "        for i, row in enumerate(matrix):\n",
    "            for j, x in enumerate(row):\n",
    "                s[i + 1][j + 1] = s[i + 1][j] + s[i][j + 1] - s[i][j] + x\n",
    "        self.s = s\n",
    "    # 返回左上角在 (r1,c1) 右下角在 (r2-1,c2-1) 的子矩阵元素和（类似前缀和的左闭右开）\n",
    "    def query(self, r1: int, c1: int, r2: int, c2: int) -> int:\n",
    "        return self.s[r2][c2] - self.s[r2][c1] - self.s[r1][c2] + self.s[r1][c1]"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
